// GenerateParentheses.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
/*
Generate ParenthesesFeb 13 '12

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()" 
*/

using namespace std;

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        vector<string> ret;
        
        if(n == 0)
        {
            return ret;
        }
        
        char* str = new char[2*n+1];
        memset(str, 0, 2*n+1);
        
        helpFun(n, n, str, ret, 0);
        delete [] str;
        
        return ret;
        
    }
    
    
    void helpFun(int l, int r, char* str, vector<string> & ret, int idx)
    {
        if (l < 0 || r < l) return;
        if(l == 0 && r == 0)
        {
            str[idx] = '\0';
            ret.push_back(string(str));
        }
        else
        {
            if(l >=1)
            {
                str[idx] = '(';
                helpFun(l-1, r, str, ret, idx+1);
            }
            if(r >=1)
            {
                str[idx] = ')';
                helpFun(l, r-1, str, ret, idx+1);
            }
            
        }
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}

